Search Results

1. E. Hyytiä and J. Virtamo, On Optimality of Single-Path Routes in Massively Dense Wireless Multi-Hop Networks, in The 10th ACM/IEEE International Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM), 2007, Crete Island, Greece (bib)

   Abstract: We consider the load balancing problem in large wireless multi-hop networks, often referred to as massively dense wireless multi-hop networks. A network is considered to be massively dense if there are nodes practically everywhere and a typical distance between two nodes is much larger than the transmission range necessitating communication over a large number of hops. The task is to choose the routes in such a way that the maximum relayed traffic load in the network is minimized. In fixed networks the multi-path routes generally yield a lower congestion and thus allow higher throughput. In contrast, we show that in the case of massively dense wireless multi-hop networks the optimal load balancing can be achieved by single-path routing. In particular, we show how any given multi-path routing can be transformed to a single-path routing with at least the same level of performance. The concepts are illustrated by numerical examples where the network nodes are assumed to reside inside a unit disk with uniform traffic demands. The shortest path routes, corresponding to straight line segments, yield a maximum traffic load of 0.637, whereas the single-path routes obtained by numerical optimization yield 0.343, corresponding to $46\%$ reduction in the traffic load.